/*  Small compiler - Staging buffer and optimizer
 *
 *  The staging buffer
 *  ------------------
 *  The staging buffer allows buffered output of generated code, deletion
 *  of redundant code, optimization by a tinkering process and reversing
 *  the ouput of evaluated expressions (which is used for the reversed
 *  evaluation of arguments in functions).
 *  Initially, stgwrite() writes to the file directly, but after a call to
 *  stgset(TRUE), output is redirected to the buffer. After a call to
 *  stgset(FALSE), stgwrite()'s output is directed to the file again. Thus
 *  only one routine is used for writing to the output, which can be
 *  buffered output or direct output.
 *
 *  staging buffer variables:   stgbuf  - the buffer
 *                              stgidx  - current index in the staging buffer
 *                              staging - if true, write to the staging buffer;
 *                                        if false, write to file directly.
 *
 *  Copyright (c) ITB CompuPhase, 1997-2003
 *
 *  This software is provided "as-is", without any express or implied warranty.
 *  In no event will the authors be held liable for any damages arising from
 *  the use of this software.
 *
 *  Permission is granted to anyone to use this software for any purpose,
 *  including commercial applications, and to alter it and redistribute it
 *  freely, subject to the following restrictions:
 *
 *  1.  The origin of this software must not be misrepresented; you must not
 *      claim that you wrote the original software. If you use this software in
 *      a product, an acknowledgment in the product documentation would be
 *      appreciated but is not required.
 *  2.  Altered source versions must be plainly marked as such, and must not be
 *      misrepresented as being the original software.
 *  3.  This notice may not be removed or altered from any source distribution.
 *
 *  Version: $Id: embryo_cc_sc7.c 56354 2011-01-29 03:19:51Z raster $
 */

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>		/* for atoi() */
#include <string.h>
#include <ctype.h>

#include "embryo_cc_sc.h"

#if defined _MSC_VER
#pragma warning(push)
#pragma warning(disable:4125)	/* decimal digit terminates octal escape sequence */
#endif

#include "embryo_cc_sc7.scp"

#if defined _MSC_VER
#pragma warning(pop)
#endif

static void stgstring(char *start, char *end);
static void stgopt(char *start, char *end);

#define sSTG_GROW   512
#define sSTG_MAX    20480

static char *stgbuf = NULL;
static int stgmax = 0; /* current size of the staging buffer */

#define CHECK_STGBUFFER(index) if ((int)(index)>=stgmax) grow_stgbuffer((index)+1)

static void grow_stgbuffer(int requiredsize) {
	char *p;
	int clear = !stgbuf; /* if previously none, empty buffer explicitly */

	assert(stgmax < requiredsize);
	/* if the staging buffer (holding intermediate code for one line) grows
	 * over a few kBytes, there is probably a run-away expression
	 */
	if (requiredsize > sSTG_MAX)
		error(102, "staging buffer"); /* staging buffer overflow (fatal error) */
	stgmax = requiredsize + sSTG_GROW;
	if (stgbuf)
		p = (char *) realloc(stgbuf, stgmax * sizeof(char));
	else
		p = (char *) malloc(stgmax * sizeof(char));
	if (!p)
		error(102, "staging buffer"); /* staging buffer overflow (fatal error) */
	stgbuf = p;
	if (clear)
		*stgbuf = '\0';
}

void stgbuffer_cleanup(void) {
	if (stgbuf) {
		free(stgbuf);
		stgbuf = NULL;
		stgmax = 0;
	} /* if */
}

/* the variables "stgidx" and "staging" are declared in "scvars.c" */

/*  stgmark
 *
 *  Copies a mark into the staging buffer. At this moment there are three
 *  possible marks:
 *     sSTARTREORDER    identifies the beginning of a series of expression
 *                      strings that must be written to the output file in
 *                      reordered order
 *    sENDREORDER       identifies the end of 'reverse evaluation'
 *    sEXPRSTART + idx  only valid within a block that is evaluated in
 *                      reordered order, it identifies the start of an
 *                      expression; the "idx" value is the argument position
 *
 *  Global references: stgidx  (altered)
 *                     stgbuf  (altered)
 *                     staging (referred to only)
 */
void stgmark(char mark) {
	if (staging) {
		CHECK_STGBUFFER(stgidx);
		stgbuf[stgidx++] = mark;
	} /* if */
}

static int filewrite(char *str) {
	if (sc_status == statWRITE)
		return sc_writeasm(outf, str);
	return TRUE;
}

/*  stgwrite
 *
 *  Writes the string "st" to the staging buffer or to the output file. In the
 *  case of writing to the staging buffer, the terminating byte of zero is
 *  copied too, but... the optimizer can only work on complete lines (not on
 *  fractions of it. Therefore if the string is staged, if the last character
 *  written to the buffer is a '\0' and the previous-to-last is not a '\n',
 *  the string is concatenated to the last string in the buffer (the '\0' is
 *  overwritten). This also means an '\n' used in the middle of a string isn't
 *  recognized and could give wrong results with the optimizer.
 *  Even when writing to the output file directly, all strings are buffered
 *  until a whole line is complete.
 *
 *  Global references: stgidx  (altered)
 *                     stgbuf  (altered)
 *                     staging (referred to only)
 */
void stgwrite(char *st) {
	int len;

	CHECK_STGBUFFER(0);
	if (staging) {
		if (stgidx >= 2 && stgbuf[stgidx - 1] == '\0'
				&& stgbuf[stgidx - 2] != '\n')
			stgidx -= 1; /* overwrite last '\0' */
		while (*st != '\0') { /* copy to staging buffer */
			CHECK_STGBUFFER(stgidx);
			stgbuf[stgidx++] = *st++;
		} /* while */
		CHECK_STGBUFFER(stgidx);
		stgbuf[stgidx++] = '\0';
	} else {
		CHECK_STGBUFFER(strlen(stgbuf) + strlen(st) + 1);
		strcat(stgbuf, st);
		len = strlen(stgbuf);
		if (len > 0 && stgbuf[len - 1] == '\n') {
			filewrite(stgbuf);
			stgbuf[0] = '\0';
		} /* if */
	} /* if */
}

/*  stgout
 *
 *  Writes the staging buffer to the output file via stgstring() (for
 *  reversing expressions in the buffer) and stgopt() (for optimizing). It
 *  resets "stgidx".
 *
 *  Global references: stgidx  (altered)
 *                     stgbuf  (referred to only)
 *                     staging (referred to only)
 */
void stgout(int index) {
	if (!staging)
		return;
	stgstring(&stgbuf[index], &stgbuf[stgidx]);
	stgidx = index;
}

typedef struct {
	char *start, *end;
} argstack;

/*  stgstring
 *
 *  Analyses whether code strings should be output to the file as they appear
 *  in the staging buffer or whether portions of it should be re-ordered.
 *  Re-ordering takes place in function argument lists; Small passes arguments
 *  to functions from right to left. When arguments are "named" rather than
 *  positional, the order in the source stream is indeterminate.
 *  This function calls itself recursively in case it needs to re-order code
 *  strings, and it uses a private stack (or list) to mark the start and the
 *  end of expressions in their correct (reversed) order.
 *  In any case, stgstring() sends a block as large as possible to the
 *  optimizer stgopt().
 *
 *  In "reorder" mode, each set of code strings must start with the token
 *  sEXPRSTART, even the first. If the token sSTARTREORDER is represented
 *  by '[', sENDREORDER by ']' and sEXPRSTART by '|' the following applies:
 *     '[]...'     valid, but useless; no output
 *     '[|...]     valid, but useless; only one string
 *     '[|...|...] valid and useful
 *     '[...|...]  invalid, first string doesn't start with '|'
 *     '[|...|]    invalid
 */
static void stgstring(char *start, char *end) {
	char *ptr;
	int nest, argc, arg;
	argstack *stack;

	while (start < end) {
		if (*start == sSTARTREORDER) {
			start += 1; /* skip token */
			/* allocate a argstack with sMAXARGS items */
			stack = (argstack *) malloc(sMAXARGS * sizeof(argstack));
			if (!stack)
				error(103); /* insufficient memory */
			nest = 1; /* nesting counter */
			argc = 0; /* argument counter */
			arg = -1; /* argument index; no valid argument yet */
			do {
				switch (*start) {
				case sSTARTREORDER:
					nest++;
					start++;
					break;
				case sENDREORDER:
					nest--;
					start++;
					break;
				default:
					if ((*start & sEXPRSTART) == sEXPRSTART) {
						if (nest == 1) {
							if (arg >= 0)
								stack[arg].end = start - 1; /* finish previous argument */
							arg = (unsigned char) *start - sEXPRSTART;
							stack[arg].start = start + 1;
							if (arg >= argc)
								argc = arg + 1;
						} /* if */
						start++;
					} else {
						start += strlen(start) + 1;
					} /* if */
					break;
				} /* switch */
			} while (nest); /* enddo */
			if (arg >= 0)
				stack[arg].end = start - 1; /* finish previous argument */
			while (argc > 0) {
				argc--;
				stgstring(stack[argc].start, stack[argc].end);
			} /* while */
			free(stack);
		} else {
			ptr = start;
			while (ptr < end && *ptr != sSTARTREORDER)
				ptr += strlen(ptr) + 1;
			stgopt(start, ptr);
			start = ptr;
		} /* if */
	} /* while */
}

/*  stgdel
 *
 *  Scraps code from the staging buffer by resetting "stgidx" to "index".
 *
 *  Global references: stgidx (altered)
 *                     staging (referred to only)
 */
void stgdel(int index, cell code_index) {
	if (staging) {
		stgidx = index;
		code_idx = code_index;
	} /* if */
}

int stgget(int *index, cell * code_index) {
	if (staging) {
		*index = stgidx;
		*code_index = code_idx;
	} /* if */
	return staging;
}

/*  stgset
 *
 *  Sets staging on or off. If it's turned off, the staging buffer must be
 *  initialized to an empty string. If it's turned on, the routine makes sure
 *  the index ("stgidx") is set to 0 (it should already be 0).
 *
 *  Global references: staging  (altered)
 *                     stgidx   (altered)
 *                     stgbuf   (contents altered)
 */
void stgset(int onoff) {
	staging = onoff;
	if (staging) {
		assert(stgidx == 0);
		stgidx = 0;
		CHECK_STGBUFFER(stgidx);
		/* write any contents that may be put in the buffer by stgwrite()
		 * when "staging" was 0
		 */
		if (stgbuf[0] != '\0')
			filewrite(stgbuf);
	} /* if */
	stgbuf[0] = '\0';
}

/* phopt_init
 * Initialize all sequence strings of the peehole optimizer. The strings
 * are embedded in the .EXE file in compressed format, here we expand
 * them (and allocate memory for the sequences).
 */
static SEQUENCE *sequences;

int phopt_init(void) {
	int number, i, len;
	char str[160];

	/* count number of sequences */
	for (number = 0; sequences_cmp[number].find; number++)
		/* nothing */;
	number++; /* include an item for the NULL terminator */

	if (!(sequences = (SEQUENCE *) malloc(number * sizeof(SEQUENCE))))
		return FALSE;

	/* pre-initialize all to NULL (in case of failure) */
	for (i = 0; i < number; i++) {
		sequences[i].find = NULL;
		sequences[i].replace = NULL;
		sequences[i].savesize = 0;
	} /* for */

	/* expand all strings */
	for (i = 0; i < number - 1; i++) {
		len = strexpand(str, (unsigned char *) sequences_cmp[i].find,
				sizeof str, SCPACK_TABLE);
		assert(len <= (int)(sizeof(str)));
		assert(len == (int)(strlen(str) + 1));
		sequences[i].find = (char *) malloc(len);
		if (sequences[i].find)
			strcpy(sequences[i].find, str);
		len = strexpand(str, (unsigned char *) sequences_cmp[i].replace,
				sizeof str, SCPACK_TABLE);
		assert(len <= (int)(sizeof(str)));
		assert(len == (int)(strlen(str) + 1));
		sequences[i].replace = (char *) malloc(len);
		if (sequences[i].replace)
			strcpy(sequences[i].replace, str);
		sequences[i].savesize = sequences_cmp[i].savesize;
		if (!sequences[i].find || !sequences[i].replace)
			return phopt_cleanup();
	} /* for */

	return TRUE;
}

int phopt_cleanup(void) {
	int i;

	if (sequences) {
		i = 0;
		while (sequences[i].find || sequences[i].replace) {
			if (sequences[i].find)
				free(sequences[i].find);
			if (sequences[i].replace)
				free(sequences[i].replace);
			i++;
		} /* while */
		free(sequences);
		sequences = NULL;
	} /* if */
	return FALSE;
}

#define _maxoptvars     4
#define _aliasmax       10	/* a 32-bit number can be represented in
				 * 9 decimal digits */

static int matchsequence(char *start, char *end, char *pattern,
		char symbols[_maxoptvars][_aliasmax + 1], int *match_length) {
	int var, i;
	char str[_aliasmax + 1];
	char *start_org = start;

	*match_length = 0;
	for (var = 0; var < _maxoptvars; var++)
		symbols[var][0] = '\0';

	while (*start == '\t' || *start == ' ')
		start++;
	while (*pattern) {
		if (start >= end)
			return FALSE;
		switch (*pattern) {
		case '%': /* new "symbol" */
			pattern++;
			assert(isdigit(*pattern));
			var = atoi(pattern) - 1;
			assert(var >= 0 && var < _maxoptvars);
			assert(alphanum(*start));
			for (i = 0; start < end && alphanum(*start); i++, start++) {
				assert(i <= _aliasmax);
				str[i] = *start;
			} /* for */
			str[i] = '\0';
			if (symbols[var][0] != '\0') {
				if (strcmp(symbols[var], str) != 0)
					return FALSE; /* symbols should be identical */
			} else {
				strcpy(symbols[var], str);
			} /* if */
			break;
		case ' ':
			if (*start != '\t' && *start != ' ')
				return FALSE;
			while ((start < end && *start == '\t') || *start == ' ')
				start++;
			break;
		case '!':
			while ((start < end && *start == '\t') || *start == ' ')
				start++; /* skip trailing white space */
			if (*start != '\n')
				return FALSE;
			assert(*(start + 1) == '\0');
			start += 2; /* skip '\n' and '\0' */
			if (*(pattern + 1) != '\0')
				while ((start < end && *start == '\t') || *start == ' ')
					start++; /* skip leading white space of next instruction */
			break;
		default:
			if (tolower(*start) != tolower(*pattern))
				return FALSE;
			start++;
			break;
		} /* switch */
		pattern++;
	} /* while */

	*match_length = (int) (start - start_org);
	return TRUE;
}

static char *
replacesequence(char *pattern, char symbols[_maxoptvars][_aliasmax + 1],
		int *repl_length) {
	char *lptr;
	int var;
	char *buffer;

	/* calculate the length of the new buffer
	 * this is the length of the pattern plus the length of all symbols (note
	 * that the same symbol may occur multiple times in the pattern) plus
	 * line endings and startings ('\t' to start a line and '\n\0' to end one)
	 */
	assert(repl_length != NULL);
	*repl_length = 0;
	lptr = pattern;
	while (*lptr) {
		switch (*lptr) {
		case '%':
			lptr++; /* skip '%' */
			assert(isdigit(*lptr));
			var = atoi(lptr) - 1;
			assert(var >= 0 && var < _maxoptvars);
			assert(symbols[var][0] != '\0');
			/* variable should be defined */
			*repl_length += strlen(symbols[var]);
			break;
		case '!':
			*repl_length += 3; /* '\t', '\n' & '\0' */
			break;
		default:
			*repl_length += 1;
			break;
		} /* switch */
		lptr++;
	} /* while */

	/* allocate a buffer to replace the sequence in */
	if (!(buffer = malloc(*repl_length))) {
		error(103);
		return NULL ;
	}

	/* replace the pattern into this temporary buffer */
	lptr = buffer;
	*lptr++ = '\t'; /* the "replace" patterns do not have tabs */
	while (*pattern) {
		assert((int)(lptr - buffer) < *repl_length);
		switch (*pattern) {
		case '%':
			/* write out the symbol */
			pattern++;
			assert(isdigit(*pattern));
			var = atoi(pattern) - 1;
			assert(var >= 0 && var < _maxoptvars);
			assert(symbols[var][0] != '\0');
			/* variable should be defined */
			strcpy(lptr, symbols[var]);
			lptr += strlen(symbols[var]);
			break;
		case '!':
			/* finish the line, optionally start the next line with an indent */
			*lptr++ = '\n';
			*lptr++ = '\0';
			if (*(pattern + 1) != '\0')
				*lptr++ = '\t';
			break;
		default:
			*lptr++ = *pattern;
		 break;
		} /* switch */
		pattern++;
	} /* while */

	assert((int)(lptr - buffer) == *repl_length);
	return buffer;
}

static void strreplace(char *dest, char *replace, int sub_length,
		int repl_length, int dest_length) {
	int offset = sub_length - repl_length;

	if (offset > 0) /* delete a section */
		memmove(dest, dest + offset, dest_length - offset);
	else if (offset < 0) /* insert a section */
		memmove(dest - offset, dest, dest_length);
	memcpy(dest, replace, repl_length);
}

/*  stgopt
 *
 *  Optimizes the staging buffer by checking for series of instructions that
 *  can be coded more compact. The routine expects the lines in the staging
 *  buffer to be separated with '\n' and '\0' characters.
 *
 *  The longest sequences must be checked first.
 */

static void stgopt(char *start, char *end) {
	char symbols[_maxoptvars][_aliasmax + 1];
	int seq, match_length, repl_length;

	assert(sequences != NULL);
	while (start < end) {
		if ((sc_debug & sNOOPTIMIZE) != 0 || sc_status != statWRITE) {
			/* do not match anything if debug-level is maximum */
			filewrite(start);
		} else {
			seq = 0;
			while (sequences[seq].find) {
				assert(seq >= 0);
				if (matchsequence(start, end, sequences[seq].find, symbols,
						&match_length)) {
					char *replace = replacesequence(sequences[seq].replace,
							symbols, &repl_length);
					/* If the replacement is bigger than the original section, we may need
					 * to "grow" the staging buffer. This is quite complex, due to the
					 * re-ordering of expressions that can also happen in the staging
					 * buffer. In addition, it should not happen: the peephole optimizer
					 * must replace sequences with *shorter* sequences, not longer ones.
					 * So, I simply forbid sequences that are longer than the ones they
					 * are meant to replace.
					 */
					assert(match_length >= repl_length);
					if (match_length >= repl_length) {
						strreplace(start, replace, match_length, repl_length,
								(int) (end - start));
						end -= match_length - repl_length;
						free(replace);
						code_idx -= sequences[seq].savesize;
						seq = 0; /* restart search for matches */
					} else {
						/* actually, we should never get here (match_length<repl_length) */
						assert(0);
						seq++;
					} /* if */
				} else {
					seq++;
				} /* if */
			} /* while */
			assert(sequences[seq].find == NULL);
			filewrite(start);
		} /* if */
		assert(start < end);
		start += strlen(start) + 1; /* to next string */
	} /* while (start<end) */
}

#undef SCPACK_TABLE
